package q210_findOrder;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    /*
    相较于207题 只需要找出一种上课的顺序即可
    那么我们只需要新建一个数组
    然后随着队列的出入栈 将课程加入到数组中
    最后判断是否能够上完所有课 按照结果返回即可
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses], order = new int[numCourses];
        List<List<Integer>> adjTable = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < numCourses; i++) {
            adjTable.add(new ArrayList<>());
        }

        for (int[] pre : prerequisites) {
            inDegree[pre[0]]++;
            adjTable.get(pre[1]).add(pre[0]);
        }

        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);

        }
        int index = 0;
        while (!queue.isEmpty()) {
            int temp = queue.poll();

            order[index] = temp;
            index++;

            for (int course : adjTable.get(temp)) {
                inDegree[course]--;
                if (inDegree[course] == 0) queue.offer(course);
            }

        }

        return index == numCourses ? order : new int[]{};
    }
}
